/*
Source : https://leetcode.com/problems/reverse-integer/
Author : nflush@outlook.com
Date   : 2016-05-05
*/

/*
11. Container With Most Water  
Total Accepted: 76940 Total Submissions: 222094 Difficulty: Medium

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Subscribe to see which companies asked this question
*/


class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0,right = height.size() -1;
        int leftH = height[left], rightH = height[right];
        int volume = min(leftH, rightH) * (right - left);
        int volumeTmp = volume;
        while(left != right){
            if (leftH < rightH){
                do{
                    left++;
                }while(height[left] <= leftH);
                if (left == right){
                    break;
                }
                leftH = height[left];
            } else {
                do{
                    right--;
                }while(height[right] < rightH || (height[right] == rightH && left != right));
                if (left == right){
                    break;
                }
                rightH = height[right];
            }
            volumeTmp = min(leftH, rightH) * (right - left);
            volume = max(volume, volumeTmp);
        }
        return volume;
    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0,right = height.size() -1;
        int leftH = height[left], rightH = height[right];
        int volume = 0;
        int volumeTmp = 0;
        while(left != right){
            if (leftH < rightH){
                volumeTmp = leftH * (right - left);
                do{
                    left++;
                }while(height[left] <= leftH);
                if (left == right){
                    break;
                }
                leftH = height[left];
            } else {
                volumeTmp = rightH * (right - left);
                do{
                    right--;
                }while(height[right] < rightH || (height[right] == rightH && left != right));
                if (left == right){
                    break;
                }
                rightH = height[right];
            }
            if (volumeTmp > volume){
                volume = volumeTmp;
            }
        }
        if (volumeTmp > volume){
            volume = volumeTmp;
        }
        return volume;
    }
};


int maxArea(int* height, int heightSize) {
    int left = 0,right = heightSize -1;
    int leftH = height[left], rightH = height[right];
    int volume = 0;
    int volumeTmp = 0;
    while(left != right){
        if (leftH < rightH){
            volumeTmp = leftH * (right - left);
            do{
                left++;
            }while(height[left] <= leftH);
            if (left == right){
                break;
            }
            leftH = height[left];
        } else {
            volumeTmp = rightH * (right - left);
            do{
                right--;
            }while(height[right] < rightH || (height[right] == rightH && left != right));
            if (left == right){
                break;
            }
            rightH = height[right];
        }
        if (volumeTmp > volume){
            volume = volumeTmp;
        }
    }
    if (volumeTmp > volume){
        volume = volumeTmp;
    }
    return volume;
}
